This application claims priority to GB Application No. 0801137.1 filed Jan. 22, 2008, the entire contents of which is incorporated herein by reference.
1. Field of the Invention
The present invention relates to an apparatus and method for performing permutation operations on data.
Data processing applications such as signal processing applications typically require data rearrangement to be performed at high data rates. When data processing is sufficiently accelerated, for example, when using a single instruction multiple data (SIMD) engine, then data rearrangements such as permutation can become a bottle-neck in performing the computations.
In signal processing applications such as those used in radio standards very common forms of permutations are de-interleave operations and interleave operations. These operations are performed in order to separate two or more channels in the case of the de-interleaving or to combine two or more channels in the case of interleaving. One example is the separation of data channels from pilot channels (i.e. control channels). Error correction is commonly used in signal processing to correct errors that can arise due to transmission of data across a noisy communication channel. During error correction processing puncturing and de-puncturing of data is often performed. Puncturing is used to vary the tradeoff between data rate and error robustness. The puncturing operation involves de-interleaving data channels and throwing away the second channel whereas de-puncturing involves interleaving one communication channel with zeros.
2. Description of the Prior Art
It is known to perform de-interleaving operations using a plurality of butterfly permutation networks in parallel. For example, the publication “Comparing Fast Implementations of Bit Permutation Instructions”, by Y. Hilewitz, Z. Shee and R Lee, Proceedings of 38th Annual Asilomar Conference on Signals, Systems and Computers, November 2004 describes how a GRP instruction, which performs a de-interleave operation, is implemented on two butterfly networks in parallel. This publication states that GRP cannot be performed on a butterfly or inverse butterfly network, but that two inverse butterfly networks may be used to group the R bits and L bits in parallel. One butterfly network de-interleaves a first channel and the other butterfly network de-interleaves a second channel. However, this technique cannot be used to perform interleave operations, only de-interleave operations. It is also known to perform generic permutation instructions using cross-bar arrangements. However, such cross-bar networks involve the order of n2 computations for an n-input cross-bar. Accordingly, such cross-bar networks are not very area-efficient.
Thus there is a requirement to provide accelerated data permutation operations in a more efficient way. There is also a requirement to be able to perform interleave operations using a butterfly permutation network.